/*
 * 035. 翻转链表
 * 翻转一个链表
 * https://www.lintcode.com/problem/reverse-linked-list/description
 * 
 * 样例
 * 给出一个链表1->2->3->null，这个翻转后的链表为3->2->1->null
 * 
 * 挑战
 * 在原地一次翻转完成
 * 
 * 2018.06.25 @jeyming
 */
package reverse_linked_list_0035;

import java.util.ArrayList;
import java.util.List;

//Definition for ListNode
class ListNode {
	int val;
	ListNode next;
	ListNode(int x) {
		val = x;
		next = null;
	}
}

public class Reverse_linked_list_0035 {
	/**
	 * @param head: n
	 * @return: The new head of reversed linked list.
	 */
	public ListNode reverse(ListNode head) {
		// write your code here
		List<Integer> list = new ArrayList<Integer>();
		int cnt = 0;
		ListNode p = head;
		while(p != null) {
			list.add(p.val);
			p = p.next;
			++cnt;
		}
		p = head;
		while(p != null && cnt >= 0) {
			p.val = list.get(--cnt);
			p = p.next;
		}
		return head;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
